#ifndef LINKEDLIST_H_INCLUDED
#define LINKEDLIST_H_INCLUDED

#include "Atomic.h"
#include "IteratorForward.h"

namespace CEngine {

template<class Element>
class LinkedList {
        struct Link;
        struct ListIterator;

    public:

        ///Creates an empty LinkedList.
        ///isPossessive defaults to true, elements will be destroyed by the list and should not be freed.
        LinkedList(void);

        ///Creates a LinkedList numberOfElements long, elements use the default constructor.
        ///If isPossessive is true elements will be destroyed by the list and should not be freed.
        LinkedList(const U64 numberOfElements, const bool isPossessive = true);

        ///Creates a LinkedList numberOfElements long, elements are all set to defaultValue.
        ///If isPossessive is true elements will be destroyed by the list and should not be freed.
        LinkedList(const U64 numberOfElements, const Element& defaultValue, const bool isPossessive = true);

        ///Creates a LinkedList made of the elements between first and last (including first, but not last).
        ///If isPossessive is true elements will be copied.
        LinkedList(const Iterator<Element>& first, const Iterator<Element>& last, const bool isPossessive = true);

        ///Creates a copy of LinkedList. Copies possessiveness.
        LinkedList(const LinkedList& List);

        ///Creates a copy of LinkedList.
        ///If isPossessive is true elements will be copied from list.
        LinkedList(const LinkedList& List, const bool isPossessive);

        ///Copies the contents of LinkedList, if possessive is true previous elements are destroyed.
        LinkedList&
        operator= (const LinkedList& List);

        ///Destructor, elements are only destroyed if possessive is true.
        ~LinkedList(void);

        ///Iterator function. Returns an iterator to the first element in the list.
        ListIterator
        begin(void) const;

        ///Iterator function. Returns an iterator to the last element in the list.
        ListIterator
        rBegin(void) const;

        ///Iterator function. Returns an iterator to the element after the end of the list.
        ///Do not dereference.
        ListIterator
        end(void) const;

        ///Access function. Returns the element at the front of the list.
        ///Doesn't change the current position
        Element&
        front(void) const;

        ///Access function. Returns the element at the end of the list.
        ///Doesn't change the current position
        Element&
        back(void) const;

        ///Adds element to the front of the list.
        void
        pushFront(const Element& element);

        ///Deletes the first element in the list.
        void
        popFront(void);

        ///Adds element to the end of the list.
        void
        pushBack(const Element& element);

        ///Deletes the last element in the list.
        void
        popBack(void);

        ///Inserts element at the given position.
        ///If position >= size element is added to the end of the list.
        void
        insert(const Iterator<Element>& position, const Element& element);

        ///Inserts a group of elements all equal to element.
        ///If position >= size element is added to the end of the list.
        ///If possessive isn't true only one element will be added, if it's true element is copied,
        ///but must still be freed afterwards.
        void
        insert(const Iterator<Element>& position, const U64 numberOfElements, const Element& element);

        ///Removes the element at postion.
        ///If position >= size the last element in the list is removed.
        ///If possessive is true the element is destroyed.
        void
        erase(const Iterator<Element>& position);

        ///Removes every element between (and including) first and last.
        ///fails if first > last. If last >= size everything after first is deleted.
        ///If possessive is true the element is destroyed.
        void
        erase(const Iterator<Element>& first, const Iterator<Element>& last);

        ///Changes the number of elements in the list.
        ///If numberOfElements < size and possessive is true the removed elements will be destroyed.
        ///Possessive MUST be true if numberOfElements > size. New elements will use the default constructor.
        void
        resize(const U64 numberOfElements);

        ///Changes the number of elements in the list.
        ///If numberOfElements < size and possessive is true the removed elements will be destroyed.
        ///Possessive MUST be true if numberOfElements > size. New elements are copies of element.
        void
        resize(const U64 numberOfElements, const Element& element);

        ///Removes every element from the list. If possessive is true the elements are destroyed.
        void
        clear(void);

        ///Returns if there are any elements in the list.
        bool
        isEmpty(void) const;

        ///Returns the size of the list (in elements).
        U64
        getSize(void) const;

        ///Returns if the list will delete elements.
        bool
        isPossessive(void) const;

        ///Sets if the list will delete elements.
        void
        setPossessive(const bool possessive);

    private:

        Link root;
        U64 size;
        bool possessive;

        Link&
        traverseList(const U64 position, Iterator<Element>* it = NULL) const;

        friend class Iterator<Element>;

        ///Internal link structure.
        struct Link {
            Element* element;
            Link* previous;
            Link* next;

            Link(void)
                :   element(NULL),
                    previous(NULL),
                    next(NULL)
            {}
        };

        ///Iterator initializer used by the generic Iterator class.
        struct ListIterator {
            LinkedList<Element>* basePointer;
            Link* currentPointer;
            U64 position;
        };
};

}

#include "LinkedListCore.h"

#endif // LINKEDLIST_H_INCLUDED
